package _01_第一季.树04.Tree01;

import _01_第一季.树04.printer.BinaryTreeInfo;

import java.util.LinkedList;
import java.util.Queue;

/*
    二叉树的实现
 */
public class BinaryTree<E> implements BinaryTreeInfo{
    protected int size;
    protected Node<E> root;

    protected static class Node<E>{
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        public Node(){
            this(null,null);
        }
        public Node(E element,Node<E> parent){
            this.element = element;
            this.parent = parent;
        }
        public boolean isLeaf(){
            return left == null && right == null;
        }
        public boolean hasTwoKids(){
            return left!=null && right!=null;
        }
        public boolean isLeftChild(){
            return parent!=null && this == parent.left;
        }
        public boolean isRightChild(){
            return parent!=null && this == parent.right;
        }
        public Node<E> sibling(){
            if(isLeftChild()){
                return parent.right;
            }
            if(isRightChild()){
                return parent.left;
            }
            return null;
        }

    }

    protected Node<E> createNode(E element,Node<E> parent){
        return new Node<>(element,parent);
    }

    protected int size(){
        return size;
    }

    protected boolean isEmpty(){
        return size == 0;
    }

    protected void clear(){
        root = null;
        size = 0;
    }

    //计算前驱节点
    protected Node<E> predecessor(Node<E> node){
        if(node == null) return null;
        Node<E> pre = node.left;
        if(pre!=null){
            while(pre.right!=null){
                pre = pre.right;
            }
            return pre;
        }

        while(node.parent!=null && node.isLeftChild()){
            node = node.parent;
        }
        return node.parent;
    }

    //计算后继节点
    protected Node<E> successor(Node<E> node){
        if(node == null) return null;
        Node<E> suc = node.left;
        if(suc!=null){
            while(suc.right!=null){
                suc = suc.right;
            }
            return suc;
        }

        while(node.parent!=null && node.isRightChild()){
            node = node.parent;
        }
        return node.parent;
    }

    //-----------------------------------------BST的遍历操作开始----------------------------------------------------------//

    //对外使用的遍历接口
    public static abstract class Visitor<E>{
        boolean stop;
        public abstract boolean visit(E element);
    }

    //前序
    public void preOrder(Visitor<E> visitor){
        if(visitor == null) return;
        preOrder(visitor,root);

    }

    private void preOrder(Visitor<E> visitor,Node<E> node){
        if(node == null || visitor.stop) return;

        visitor.stop = visitor.visit(node.element);
        preOrder(visitor, node.left);
        preOrder(visitor, node.right);

    }

    //中序
    public void inOrder(Visitor<E> visitor){
        if(visitor == null) return;
        inOrder(visitor,root);

    }

    private void inOrder(Visitor<E> visitor,Node<E> node){
        if(node == null || visitor.stop) return;
        inOrder(visitor, node.left);
        if(visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        inOrder(visitor, node.right);

    }

    //后序
    public void postOrder(Visitor<E> visitor){
        if(visitor == null) return;
        postOrder(visitor,root);

    }

    private void postOrder(Visitor<E> visitor,Node<E> node){
        if(node == null || visitor.stop) return;
        postOrder(visitor, node.left);
        postOrder(visitor, node.right);
        if(visitor.stop) return;
        visitor.stop = visitor.visit(node.element);

    }

    //层序遍历
    public void levelOrderTraversal(Visitor<E> visitor) {
        if (root == null || visitor == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (visitor.visit(node.element)) return;


            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    //BST的遍历操作----------------------------- BST的遍历操作结束---------------------------------------------------------------------//

    public int heightNR(){
        if(root == null) return 0;
        int levelSize = 1;
        int height = 0;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            Node<E> node = queue.poll();
            levelSize--;
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
            if(levelSize==0){
                levelSize = queue.size();
                height++;
            }
        }
        return height;
    }

    //判断是否是完全二叉树
    public boolean isComplete(){
        if(root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        boolean leaf = false;

        while(!queue.isEmpty()){
            Node<E> node = queue.poll();
            if(leaf && !node.isLeaf()) return false;

            if(node.left!=null){
                queue.offer(node.left);
            }else if(node.right!=null){ //左等于空  右不等于空
                //node.left == null && node.right != null
                return false;
            }

            if(node.right!=null){
                queue.offer(node.right);
            }else{
                //node.right == null && node.left != null
                //node.right == null && node.left == null
                leaf = true; //往后遍历的节点必须都是叶子节点
            }
        }
        return true;
    }


    //计算二叉树的高度 递归
    public int height(){
        return height(root);
    }

    private int height(Node<E> node){
        if(node == null) return 0;
        return 1 + Math.max(height(node.left),height(node.right));
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>)node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>)node).right;
    }

    @Override
    public Object string(Object node) {
        /*Node<E> myNode = ((Node<E>)node);
        String parentString = "null";
        if(myNode.parent!=null){
            parentString = myNode.parent.element.toString();
        }
        return myNode.element+"_p("+parentString+")";*/
        return node;
    }
}
